package KMP;

/**
 * @version 1.0
 * @Author jsc
 * @Date 2025/4/20 16:22
 * @注释 KMP算法实现
 */
public class KMP {
    public static void getNext(int[] next, String pattern) {
        next[0] = 0;
        int j = 0;

        for (int i = 1; i < pattern.length(); i++) {
            while (j != 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = next[j - 1];
            }

            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++;
            }
            next[i] = j;
        }
    }

    public static void main(String[] args) {
        String haystack = "fadbutsad";
        String needle = "sad";

        int m = haystack.length();
        int n = needle.length();
        int[] next = new int[n];
        int ans = -1;

        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < m; i++) {
            while (j != 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }

            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }

            if (j == n) {
                ans = i - n + 1;
                break;
            }
        }

        System.out.println(ans);
    }
}
